//https://leetcode.cn/problems/regular-expression-matching/


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = ' ' + s;
        p = ' ' + p;
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(s[i] == p[j] || p[j] == '.') dp[i][j] = dp[i - 1][j - 1];
                else if(p[j] == '*')
                {
                    if(p[j - 1] == '.')
                    {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    }
                    else
                    {
                        dp[i][j] = dp[i][j - 2] || (s[i] == p[j - 1] && dp[i - 1][j]);
                    } 
                } 
                else dp[i][j] = false; 
            }
        }
        return  dp[m][n];
    }
};